//路径总和
class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) 
    {
       if(root==nullptr) return false;
       return dfs(root,targetSum-root->val);
    }
    bool dfs(TreeNode* root, int targetSum)
    {
        if(!root->right && !root->left && targetSum==0)
        {
            return true;
        }
        else if(!root->right && !root->left)
        {
            return false;
        }
        if(root->left)
        {
            if(dfs(root->left,targetSum-root->left->val)) return true;
        }
        if(root->right)
        {
            if(dfs(root->right,targetSum-root->right->val)) return true;
        }
        return false;

    }
};
//路径总和II
class Solution {
public:
    vector<int>tmp;
    vector<vector<int>>res;
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) 
    {
        if(root==nullptr) return res;
        tmp.push_back(root->val);
        dfs(root,targetSum-root->val);
        return res;
    }
    void dfs(TreeNode* root , int targetSum)
    {
        if(!root->left && !root->right)
        {
            if(targetSum==0)
            {
                res.push_back(tmp);
            }
            return;
        }
        if(root->left)
        {
            tmp.push_back(root->left->val);
            dfs(root->left,targetSum-root->left->val);
            tmp.pop_back();
        }
        if(root->right)
        {
            tmp.push_back(root->right->val);
            dfs(root->right,targetSum-root->right->val);
            tmp.pop_back();
        }
    }
};

//二叉搜索树的最近公共祖先
class Solution {
public:
    //思路： 利用二叉搜索树的有序性
    //情况一：
    //如果 p q都大于 root 说明 p q都在root的右子树
    //反之都在 root的左子树
    //一旦一个大于 一个小于 那么当前节点就是最近的公共祖先
    //情况二：
    //除此之外 还需要处理 p是q的子树 或者反过来的情况
    //那只要我遍历到q || p 直接返回即可 无须判断它的子树中是否有q || p
    //因为如果没有q || p 那么又回到了第一种情况。
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) 
    {
        if(root ==q || root== p || root==nullptr) return root;
        if(root->val > p->val && root->val >q->val)
        {
            return lowestCommonAncestor(root->left,p,q);
        }
        else if(root->val < q->val && root->val < p->val)
        {
            return lowestCommonAncestor(root->right,p,q);
        }
        else
        {
            return root;
        }
    }
};
//二叉搜索树的插入操作
//递归法
class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) 
    {
        if(root==nullptr)
        {
            //找到了插入位置
            TreeNode* node=new TreeNode(val);
            return node;
        }
        if(root->val > val)
        {
            root->left=insertIntoBST(root->left,val);
        }
        if(root->val < val)
        {
            root->right=insertIntoBST(root->right,val);
        }   
        return root;
    }
};

//迭代法
class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) 
    {
        if(root==nullptr)
        {
            TreeNode* node=new TreeNode(val);
            return node;
        }
        TreeNode *pre=nullptr;
        TreeNode* cur=root;
        while(cur)
        {
            if(cur->val < val)
            {
                pre=cur;
                cur=cur->right;
            }
            else if(cur->val > val)
            {
                pre=cur;
                cur=cur->left;
            }
        }
        cur = new TreeNode(val);
        if (pre->val < val)
        {
            pre->right =cur;
        }
        else
        {
            pre->left = cur;
        }
        return root;
    }
};
